1. Field of the Invention
This invention relates generally to computer program execution systems, e.g., optimizing compilers, and more specifically, to a sampling-based method and data structures for characterizing a program's execution by periodic call stack inspection during runtime.
2. Discussion of the Prior Art
Many modern programming language runtime environments and tools can benefit from runtime feedback from a program. For example, Java Virtual Machines (JVM) may use runtime feedback to guide optimization of the running program. As another example, program understanding tools may gather runtime information and report summaries to the user. An adaptive optimization system attempts to optimize an executing program based on its current execution. Such systems typically identify sections of the program where significant runtime is spent and recompiles those sections with an optimizing compiler.
Thus, a number of research projects have explored more aggressive forms of dynamic compilation: These projects have been described in the following references: “Fast, effective dynamic compilation”, Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, pages 149—159, Philadelphia, Pa., 21-24 May 1996, and SIGPLAN Notices, 31(5), May 1996 to J. Auslander, et al.; “Dynamo: A transparent dynamic optimization system”, SIGPLAN 2000 Conference on Programming Language Design and Implementation, June 2000 to V. Bala, et al.; “Efficient Compilation and Profile-Driven Dynamic Recompilation in Scheme”, PhD thesis, Indiana University, 1997 to R. G. Burger; “An infrastructure for profile-driven dynamic recompilation”, ICCL'98, the IEEE Computer Society International Conference on Computer Languages, May 1998, to R. G. Burger et al.; “A general approach for run-time specialization and its application to C”, Conference Record of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages}, pages 145-156, January 1996 by C. Consel et al.; “DyC: An expressive annotation-directed dynamic compiler for C”, Technical Report TR-97-03-03, University of Washington, Department of Computer Science and Engineering, March 1997 by B. Grant, et al.; “An evaluation of staged run-time optimizations in DyC”, Proceedings of the ACM SIGPLAN'99 Conference on Programming Language Design and Implementation, pages 293-304, 1999 by B. Grant, et al.; “Continuous Program Optimization”, PhD thesis, University of California, Irvine, 1999 by T. P. Kistler; “Dynamic specialization in the Fabius system”, ACM Computing Surveys, 30(3es):1-5, Sep. 1998, Article 23 by M. Leone et al.; “Efficient incremental run-time specialization for free”, Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pages 281—292, 1999, by R. Marlet, et al.; and, “A system for fast, flexible, and high-level dynamic code generation”, Proceedings of the ACM SIGPLAN'97 Conference on Programming Language Design and Implementation (PLDI), pages 109-121, Las Vegas, Nev., 15-18 Jun. 1997, and SIGPLAN Notices 32(5), May 1997, by M. Poletto, et al. These aggressive forms of dynamic compilation use runtime information to tailor the executable to its current environment. Most of these systems are not fully automatic, and so far, few of these techniques have appeared in mainstream JVMs. However, these systems have demonstrated that online feedback-directed optimizations can yield substantial performance improvements.
Previous work, such as the Self-93 system is described in aforementioned “Reconciling responsiveness with performance in pure object-oriented languages”, ACM Transactions on Programming Languages and Systems, 18(4):355-400, July 1996 to Hölzle, et al. In the Self-93 work the call stack is examined when an invocation counter threshold is reached with the goal of determining which active method on the call stack is a likely candidate to be compiled. The method to be compiled is chosen using parameterizable heuristics, such as the size of a method. Thus, in the Self-93 system, the methods that are on the call stack are neither recorded nor used to determine the runtime behavior of an application.
It would be highly desirable to provide a novel system and method for examining the call stack of a running application and gathering information as the stack is traversed which can be used to determine the runtime behavior of an application.
It would be further highly desirable to provide a novel system and method for examining the call stack of a running application having low overhead for driving adaptive and online feedback-directed optimizations.